The amount of memory available in computers has grown at an exponential pace. It is not uncommon for personal computers to have more than a gigabyte of memory. However, the demand for memory has grown exponentially as well. Video games, movies, high resolution graphics, and complex software all require large amounts of memory. To meet the vast requirements for memory, operating systems designed to control computers have historically supplemented physical memory with virtual memory. Virtual memory is usually supported by another storage medium that is larger than the physical memory or random access memory (RAM). For example, a hard disk drive can be used to store information when a computer's memory needs exceed the physical memory that exists.
Physical and virtual memory may be allocated to processes and programs by the operating system in portions of memory called pages. Each page can represent a minimum predetermined amount of physical memory that is being allocated by the operating system. Each program can track memory usage with data structures that store or point to memory allocations of varying size. The nodes in the data structure can represent multiple pages of memory or a fraction of a page of memory. The data structure can be used by the program to manage the allocated memory.
Typically, a program running on a computer may request that a predetermined amount of memory be allocated from the operating system when the program needs storage space. For example, the program may need 100 data records worth of memory. If there are 10 data records in every page, then the operating system can allocate 10 pages of memory to the program. When the pages of memory are no longer needed, they can be de-allocated by the operating system and become free for use by another program or thread. For instance, if 10 data records are no longer needed by the program, they can be de-allocated. However, if the memory is not de-allocated efficiently, the computer may be left with 10 pages that are 90% full, where each page has one free data record instead of a free page of memory.
Allocating and de-allocating memory from the operating system can require a relatively large amount of time for a program, especially when the slower virtual memory system is accessed. In order to maximize memory usage efficiency, the program can optimize management of its already allocated memory. Thus, instead of constantly allocating and de-allocating memory from the operating system, the program can take advantage of memory already allocated to the program from the operating system that is not being used. One method for doing this is to create a list of free memory sub-pages or locations contained within the memory pages allocated to a program.
With gigabytes of memory being used in modern computers, however, the list can become very large. The resources required to organize and/or sort the list of memory that has been allocated to the program but is not being used can be greater than any benefit derived from maintaining such a list.